# Python 2.6.4
# Project Euler, Problem 187
# Copyright 2010 Talha Zaman

def sieveprimes(limit):
    from math import sqrt
    sieve = [False for i in range(0, limit/2)]
    sieve[0] = True
    lim = int(sqrt(limit))+1
    for i in range(3,lim,2):
        if sieve[i/2]: continue
        for j in range(i*i, limit, i*2):
            sieve[j/2] = True
    return [2] + [(x<<1)+1 for x in range(limit/2) if not sieve[x]]

def countprimes(primes, limit):
    pi, k, count = [0]*limit, 0, 0
    for i in xrange(2, limit):
        if k<len(primes) and primes[k] <= i:
            count += 1
            k += 1
        pi[i] = count
    return pi

lim = 100000000
sqlim = 10000
P = sieveprimes(lim/2 + 1)
pi = countprimes(P, lim/2 + 1)
total = 0
for k in xrange(1, pi[sqlim]+1):
    total += pi[int(lim/P[k-1])] - k + 1
print total
